/**
 * HowManySubsetCanDivideFromOneSet.java created by zhangzhidong 
 * at 上午9:35:48 2015年9月30日
 */
package homework;

/**
 * 当n=4时{1,2,3,4}可以划分成为15个不同的非空子集合,编程实现给定整数n,<br>
 * 计算出n个元素的集合1,2,3..n可以划分成为多少个非空子集.
 * @author Alex
 *
 */
public class HowManySubsetCanDivideFromOneSet {

	/**
	 * 上午9:35:49 2015年9月30日
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(entrance(new int[]{1,2,3,4,5,6}));
	}
	public static int entrance(int array[]){
		
		return subset(array, 0, array.length-1);
	}
	/**
	 * start end 指的是下标
	 * 上午9:49:39 2015年9月30日
	 * @param array
	 * @param start
	 * @param end
	 * @return
	 */
	public static int subset(int array[],int start,int end){
	
		if(start >= end){
			//这是只有一个元素的情况,也是返回的条件
			return 1;
		}else{
			//如果有多个元素
			return 2*subset(array ,start+1,end)+1;
			//或者
			//return subset(array,start+1,end)+subset(array,start+1,end)+1;
		}	
	}
	

}
